package org.example.myleet.p773;

import java.util.*;

public class Solution {

    private static final int[][] TARGET = new int[][]{{1,2,3},{4,5,0}};

    private static final int[][] DIRECTIONS = new int[][]{{-1,0}, {0,1}, {1,0}, {0,-1}};

    public int slidingPuzzle(int[][] board) {
        if (isUnlock(board)) {
            return 0;
        }
        int count = 1;
        Set<String> visited = new HashSet<>();
        Deque<int[][]> stack = new LinkedList<>();
        stack.push(board);
        while (!stack.isEmpty()) {
            List<int[][]> nextSteps = new ArrayList<>(stack.size() * 3);
            while (!stack.isEmpty()) {
                int[][] step = stack.pop();
                List<int[][]> nextStates = nextStates(step);
                for (int[][] nextState : nextStates) {
                    String state = serializeBoard(nextState);
                    if (visited.contains(state)) {
                        continue;
                    }
                    if (isUnlock(nextState)) {
                        return count;
                    }
                    nextSteps.add(nextState);
                    visited.add(state);
                }
            }
            for (int[][] nextStep : nextSteps) {
                stack.push(nextStep);
            }
            ++count;
        }
        return -1;
    }

    private List<int[][]> nextStates(int[][] board) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    List<int[][]> nextStates = new ArrayList<>(4);
                    for (int k = 0; k < 4; ++k) {
                        int[] direction = DIRECTIONS[k];
                        int newI = i + direction[0];
                        int newJ = j + direction[1];
                        if (newI > 1 || newI < 0 || newJ > 2 || newJ < 0) {
                            continue;
                        }
                        int[][] copy = copyBoard(board);
                        int t = copy[i][j];
                        copy[i][j] = copy[newI][newJ];
                        copy[newI][newJ] = t;
                        nextStates.add(copy);
                    }
                    return nextStates;
                }
            }
        }
        throw new RuntimeException("题目数据有病，找不到0位置");
    }

    private int[][] copyBoard(int[][] board) {
        int[][] copy = new int[2][3];
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                copy[i][j] = board[i][j];
            }
        }
        return copy;
    }

    private String serializeBoard(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    private boolean isUnlock(int[][] board) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] != TARGET[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
